package org.basic.algorithm.simple;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 简单算法
 *
 * @author LiKun
 * @date 2021/10/8 11:05
 */
public class SimpleAlgorithm {
    /**
     * 获取该对象的一个实例
     *
     * @return ArrayAlgorithm
     */
    public static SimpleAlgorithm getInstance() {
        return new SimpleAlgorithm();
    }

    /**
     * 找出给定数组(target)的中心索引并返回
     * 中心索引：该索引的左边值之和 == 该索引的右边值之和
     * 注：若存在多个中心索引则返回最左面的一个，若不存在则返回-1
     * 注：1 < target.length < 10000 && -1000 < target[X] < 1000
     * 地址：https://leetcode-cn.com/problems/find-the-middle-index-in-array/solution/
     * <p>
     * 优化：将Arrays.stream(target).summaryStatistics().getSum()替换为增强for循环；
     * 优势：提高执行时间，减少运行时内存
     *
     * @param target 给定的数组
     *
     * @return 中心索引
     */
    public int getCenterIndex(int[] target) {
        int sum = 0, index = 0, leftSum = 0;

        // 计算该数组所有元素之和
        for (int value : target) {
            sum += value;
        }

        // 遍历寻找中心索引(找到则直接返回)
        do {
            if (leftSum << 1 != sum - target[index]) {
                leftSum += target[index++];
            } else {
                return index;
            }
        } while (index < target.length);

        return -1;
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * 找出数组(target)中给定值(value)的下标，如果存在则返回，否则返回其应该被插入的位置
     * 注：数组(target)为无重复数据的升序排列数组；1 < target.length < 10000 && -1000 < target[X] && value < 1000
     * <p>
     * 注：终止条件非常重要
     *
     * @param target 无重复数据的升序排列数组
     * @param value  给定的特定值
     *
     * @return 数组下标索引
     */
    public int findSearchIndex(int[] target, int value) {
        // 使用索引求解
        return findSearchIndexOfIndex(target, value);
        // 使用递归求解
//        return findSearchIndexOfRecursive(target, value);
    }

    /**
     * 使用索引处理寻找给定值的索引（SELF）
     *
     * @param target 无重复数据的升序排列数组
     * @param value  给定的特定值
     *
     * @return 数组下标索引
     */
    public int findSearchIndexOfIndex(int[] target, int value) {
        // left：左边界索引；right：右边界索引；index：中间节点索引
        int index, left = 0, right = target.length - 1;

        while (left <= right) {
            index = (left + right) >> 1;

            if (value == target[index]) {
                return index;
            } else if (value > target[index]) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }

        return left;
    }

    /**
     * 使用递归处理寻找给定值的索引
     * 注：该方法效率较低，优化后可成为：findSearchIndexOfIndex
     *
     * @param target 无重复数据的升序排列数组
     * @param value  给定的特定值
     *
     * @return 数组下标索引
     */
    public int findSearchIndexOfRecursive(int[] target, int value) {
        if (target.length == 1) {
            // 递归结束条件
            return value <= target[0] ? 0 : 1;
        } else if (target.length == 2) {
            // 递归结束条件
            return value <= target[0] ? 0 : (value <= target[1] ? 1 : 2);
        } else {
            int index = target.length >> 1;

            if (value <= target[index]) {
                int[] left = new int[index];
                System.arraycopy(target, 0, left, 0, index);

                // 递归处理左面的数组
                return findSearchIndex(left, value);
            } else {
                int[] right = new int[target.length - index - 1];
                System.arraycopy(target, index + 1, right, 0, right.length);

                // 递归处理右面的数组
                return index + findSearchIndex(right, value) + 1;
            }
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * 合并给定的二维数组，保证二维数组中数据无交集
     * 例如：[[1,3],[2,6],[8,10],[15,18]] ---> [[1,6],[8,10],[15,18]]
     * 注：1 < target < 1000 && target[i].length == 2 && 0 < target[i][0] < target[i][1] < 1
     *
     * @param target 待合并数组
     *
     * @return 合并后的数组
     */
    public int[][] mergeRange(int[][] target) {
        if (target.length <= 1) {
            return target;
        } else {
//            return mergeRangeOfString(target);
            return mergeRangeOfArrayList(target);
        }
    }

    /**
     * 通过构建和解析字符串得到最终的结构
     * 注：内存占用少，但执行效率较低
     *
     * @param target 待合并数组
     *
     * @return 合并后结构
     */
    private int[][] mergeRangeOfString(int[][] target) {
        int[][] result;
        final String split = ",";

        // 初始化字符串构造器
        StringBuilder builder = new StringBuilder();
        // 根据每个数组下表为0的值进行排序
        Arrays.sort(target, Comparator.comparing(array -> array[0]));

        int[] tool = target[0];

        for (int[] array : target) {
            if (tool[1] >= array[0]) {
                tool[1] = Math.max(tool[1], array[1]);
            } else {
                builder.append(tool[0]).append(split).append(tool[1]).append(split);
                tool = array;
            }
        }

        String[] inter = builder.append(tool[0]).append(split).append(tool[1]).toString().split(split);
        result = new int[inter.length >> 1][2];

        for (int i = 0; i < result.length; i++) {
            int interIndex = i << 1;
            result[i][0] = Integer.parseInt(inter[interIndex]);
            result[i][1] = Integer.parseInt(inter[interIndex + 1]);
        }

        return result;
    }

    /**
     * 通过构建和解析ArrayList得到最终的结构
     * 注：执行效率和内存占用较为均衡
     *
     * @param target 待合并数组
     *
     * @return 合并后结构
     */
    private int[][] mergeRangeOfArrayList(int[][] target) {
        // 初始化ArrayList
        List<int[]> arrayList = new ArrayList<>();
        // 根据每个数组下表为0的值进行排序
        Arrays.sort(target, Comparator.comparing(array -> array[0]));

        int[] tool = target[0];

        for (int[] array : target) {
            if (tool[1] >= array[0]) {
                tool[1] = Math.max(tool[1], array[1]);
            } else {
                arrayList.add(tool);
                tool = array;
            }
        }

        arrayList.add(tool);
        return arrayList.toArray(new int[arrayList.size()][2]);
    }
}
